//
//  Problem740.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/27.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 740. 删除并获得点数
 给你一个整数数组 nums ，你可以对它进行一些操作。

 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
  
 示例 1：
     输入：nums = [3,4,2]
     输出：6
     解释：
     删除 4 获得 4 个点数，因此 3 也被删除。
     之后，删除 2 获得 2 个点数。总共获得 6 个点数。
 示例 2：
     输入：nums = [2,2,3,3,3,4]
     输出：9
     解释：
     删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
     之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
     总共获得 9 个点数。

 提示：
     1 <= nums.length <= 2 * 104
     1 <= nums[i] <= 104
 */
@objcMembers class Problem740: NSObject {
    func solution() {
        print(deleteAndEarn([1]))                       // 1
        print(deleteAndEarn([1,2]))                     // 2
        print(deleteAndEarn([3,4,2]))                   // 6
        print(deleteAndEarn([2,2,3,3,3,4]))             // 9
        print(deleteAndEarn([8,10,4,9,1,3,5,9,4,10]))   // 37
        print(deleteAndEarn([1,6,3,3,8,4,8,10,1,3]))    // 43
        print(deleteAndEarn([3,1]))                     // 4
        
        print(deleteAndEarn([8,3,4,7,6,6,9,2,5,8,2,4,9,5,9,1,5,7,1,4])) // 61
        
    }
    
    /*
     我们要得到最大的点数：
     动态规划
     */
    func deleteAndEarn(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        } else if nums.count == 1 {
            return nums[0]
        }
        let len = nums.max()! + 1
        var list:[Int] = Array(repeating: 0, count: len)
        for n in nums {
            list[n] += n
        }
//        print(list)
        
        var dp:[Int] = Array(repeating: 0, count: len)
        // 只有1个值时，拿走它就行
        dp[len-1] = list[len-1]
        // 有2个值，拿走这2个最大的值
        dp[len-2] = max(list[len-1], list[len-2])
        
        // 有3个值：1，2，3； 有2个情况：
        // 带走1 = num[1] + num[3]
        // 带走2 = num[2]
        // = max(num[1]+num[3], num[2])
        dp[len-3] = max(list[len-3] + list[len-1], list[len-2])
        for i in (0..<dp.count-3).reversed() {
            dp[i] = max(list[i] + dp[i+2], list[i+1] + dp[i+3])
        }
//        print(dp)
        return dp[0]
    }
    
    func deleteEarnDP(_ nums: [Int], _ dp: inout [Int], _ i: Int) -> Int {
        if dp[i] != 0 {
            return dp[i]
        }
        
        dp[i] = max(nums[i] + dp[i+2], nums[i+1] + dp[i+3])
        
        return dp[i]
    }
}
